package com.zfl;

import java.util.LinkedList;

public class LargestRectangleArea {

    public int largestRectangleArea(int[] heights) {


        LinkedList<Integer> stack = new LinkedList<>();
        int n = heights.length;
        int maxArea=0;
        for (int i = 0; i <= n; i++) {
            int currentHeight = i == n ? 0 : heights[i];

            while(!stack.isEmpty() && currentHeight<heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int left = stack.isEmpty()?-1:stack.peek();
                int right=i;
                int width = right-left-1;
                int currentArea = width*height;
                maxArea = Math.max(maxArea,currentArea);
            }

            stack.push(i);
        }
        return maxArea;
    }

}
